#include <iostream>
using namespace std;

#include <conio.h>

template <class Qtype> class MyQueue {
    typedef struct holder{
        Qtype o;
        holder *next, *prev;
    }HOLDER;

    HOLDER *first, *last;
    int size;


    public:

    MyQueue(){
        first = last = NULL; size = 0;
    }

    ~MyQueue(){

    }

    void enQueue(Qtype newElem){

        size++;
        HOLDER* newHolder = (HOLDER*)malloc(sizeof(HOLDER));
        newHolder->o = newElem;
        newHolder->next = first;
        if(size>1)
            first->prev = newHolder;
        first = newHolder;
        if(size==1)
            last = newHolder;

    }

    Qtype deQueue(){
        Qtype tempObj;

        if(first!=NULL){
            HOLDER* temp = last;
            last = temp->prev;
            size--;
            tempObj = temp->o;
            free(temp);
            return tempObj;
        }
        return NULL;
    }

    int getSize(){
        return size;
    }
};

int myPow(int integ, int e){
    if(e ==0) return 1;
    return(integ * myPow(integ, e-1));
}

int main(){
    MyQueue<int> mq;

    for(int i =0; i<10000000; i++)
        mq.enQueue(i);


    cout << "Q-size: " << mq.getSize() <<endl;

    while(mq.getSize()>1)
        mq.deQueue();


    cout << "Q-size: " << mq.getSize() <<endl;


}
